The final problem was expressed as follows:
The first part of the problem is the same Compulsory Problem. Then after having mapped the roads, a brick is set down somewhere in the road system blocking one of the roads. You are to (1) find the brick and (2) having found the brick find your way to the other side of the brick by the shortest path you can. To simplify matters slightly, you may assume that the brick blocks exactly one path, i.e., it is not sitting in the middle of an intersection. [2]
The solution to this problem considers the tiles as nodes in a graph, and searches the graph for a loop that includes the blocked tile. The search algorithm is a simulation of a breadth-first search through a series of bounded depth-first searches. The solution is as follows:
The exploration ruleset described in Section 4.2 was modified by making all of the tile states non-terminal, so execution does not stop when the entire course has been explored.
32 new tile states were added to the stateset. These new states encode the tile type and the direction from which the tile was entered when searching for a path around the obstacle. 11 of these states are artifacts of the rotation mechanism and do not appear in any rules.
Two new robot states are added, one to extend the search a level and one to return from the leaf nodes of the current search.
Finally, 72 new strategic rules were added, implementing the graph search. The new rules fall into the following categories:
1 . When the obstacle is encountered, the current tile state is changed to a state reflecting the presence of the obstacle, the focus is moved to the next tile, and the robot state is changed to the outward search state. A representative rule in this category is shown in Figure 13a.
2. When in the outbound search robot state, as long as tiles are encountered that have been searched before, the tile and robot states are unchanged and the focus moves to the next tile in the explored path. An example is shown in Figure 13b.
3. When in the inbound robot state, the focus retraces the outbound path unless either an intersection or the obstacle tile is encountered. An example is in figure 13c. Figure 13c.
4. When in the outbound search robot state, if a tile is encountered whose state is not one of the states introduced for the final problem, the tile's state is changed to the appropriate new state, the robot state is changed to the inbound state, and the direction of travel is reversed. An example of this situation is shown in Figures 13d and e. This example also shows the general mechanism that is used to change directions and then change tiles; it is also used in navigating corners and intersections.
5. If the obstacle tile is encountered when in the outbound search state, a shortest path has been found. The robot state is changed to the 'halt' state, terminating execution.
6. Each of an intersection tile's exits is explored in turn. When the intersection is encountered in the outbound tile state, the first exit to clockwise is taken. When it is encountered in the inbound tile state, the next clockwise exit is taken. If this is not the same exit as the one from which the tile was originally entered, the robot state is changed to the outbound exploration state.
Figure 14
shows the map at several steps in the search. In
Figure 14a,
the entire road course has been identified, the obstacle has been
encountered (the robot was proceeding North at the time), and its tile
marked. In
Figure 14b,
two levels of the search have been performed.
The arrows in the new tile states show the direction to exit each of
the three tiles along a shortest path to the obstacle tile. Finally,
in Figure 14c,
the search is complete.